home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Tcl-Tk 8.0 / Pre-installed version / tcl8.0 / generic / tclAlloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-15  |  10.5 KB  |  457 lines  |  [TEXT/CWIE]
  1. /* 
  2.  * tclAlloc.c --
  3.  *
  4.  *    This is a very fast storage allocator.  It allocates blocks of a
  5.  *    small number of different sizes, and keeps free lists of each size.
  6.  *    Blocks that don't exactly fit are passed up to the next larger size.
  7.  *    Blocks over a certain size are directly allocated from the system.
  8.  *
  9.  * Copyright (c) 1983 Regents of the University of California.
  10.  * Copyright (c) 1996-1997 Sun Microsystems, Inc.
  11.  *
  12.  * Portions contributed by Chris Kingsley, Jack Jansen and Ray Johnson.
  13.  *
  14.  * See the file "license.terms" for information on usage and redistribution
  15.  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  16.  *
  17.  * SCCS: @(#) tclAlloc.c 1.4 97/08/11 18:45:38
  18.  */
  19.  
  20. #include "tclInt.h"
  21. #include "tclPort.h"
  22.  
  23. #ifdef TCL_DEBUG
  24. #   define DEBUG
  25. /* #define MSTATS */
  26. #   define RCHECK
  27. #endif
  28.  
  29. typedef unsigned long caddr_t;
  30.  
  31. /*
  32.  * The overhead on a block is at least 4 bytes.  When free, this space
  33.  * contains a pointer to the next free block, and the bottom two bits must
  34.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  35.  * byte is the size index.  The remaining bytes are for alignment.
  36.  * If range checking is enabled then a second word holds the size of the
  37.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  38.  * The order of elements is critical: ov_magic must overlay the low order
  39.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  40.  */
  41.  
  42. union overhead {
  43.     union overhead *ov_next;    /* when free */
  44.     struct {
  45.     unsigned char    ovu_magic0;    /* magic number */
  46.     unsigned char    ovu_index;    /* bucket # */
  47.     unsigned char    ovu_unused;    /* unused */
  48.     unsigned char    ovu_magic1;    /* other magic number */
  49. #ifdef RCHECK
  50.     unsigned short    ovu_rmagic;    /* range magic number */
  51.     unsigned long    ovu_size;    /* actual block size */
  52. #endif
  53.     } ovu;
  54. #define ov_magic0    ovu.ovu_magic0
  55. #define ov_magic1    ovu.ovu_magic1
  56. #define ov_index    ovu.ovu_index
  57. #define ov_rmagic    ovu.ovu_rmagic
  58. #define ov_size    ovu.ovu_size
  59. };
  60.  
  61.  
  62. #define MAGIC        0xef        /* magic # on accounting info */
  63. #define RMAGIC        0x5555        /* magic # on range info */
  64.  
  65. #ifdef RCHECK
  66. #define    RSLOP        sizeof (unsigned short)
  67. #else
  68. #define    RSLOP        0
  69. #endif
  70.  
  71. #define OVERHEAD (sizeof(union overhead) + RSLOP)
  72.  
  73. /*
  74.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  75.  * smallest allocatable block is 8 bytes.  The overhead information
  76.  * precedes the data area returned to the user.
  77.  */
  78.  
  79. #define NBUCKETS    13
  80. #define MAXMALLOC    (1<<(NBUCKETS+2))
  81. static    union overhead *nextf[NBUCKETS];
  82.  
  83. #ifdef MSTATS
  84.  
  85. /*
  86.  * nmalloc[i] is the difference between the number of mallocs and frees
  87.  * for a given block size.
  88.  */
  89.  
  90. static    unsigned int nmalloc[NBUCKETS+1];
  91. #include <stdio.h>
  92. #endif
  93.  
  94. #if defined(DEBUG) || defined(RCHECK)
  95. #define    ASSERT(p)   if (!(p)) panic(# p)
  96. #define RANGE_ASSERT(p) if (!(p)) panic(# p)
  97. #else
  98. #define    ASSERT(p)
  99. #define RANGE_ASSERT(p)
  100. #endif
  101.  
  102. /*
  103.  * Prototypes for functions used only in this file.
  104.  */
  105.  
  106. static void         MoreCore _ANSI_ARGS_((int bucket));
  107.  
  108. /*
  109.  *----------------------------------------------------------------------
  110.  *
  111.  * TclpAlloc --
  112.  *
  113.  *    Allocate more memory.
  114.  *
  115.  * Results:
  116.  *    None.
  117.  *
  118.  * Side effects:
  119.  *    None.
  120.  *
  121.  *----------------------------------------------------------------------
  122.  */
  123.  
  124. char *
  125. TclpAlloc(
  126.     unsigned int nbytes)    /* Number of bytes to allocate. */
  127. {
  128.     register union overhead *op;
  129.     register long bucket;
  130.     register unsigned amt;
  131.  
  132.     /*
  133.      * First the simple case: we simple allocate big blocks directly
  134.      */
  135.     if (nbytes + OVERHEAD >= MAXMALLOC) {
  136.     op = (union overhead *)TclpSysAlloc(nbytes+OVERHEAD, 0);
  137.     if (op == NULL) {
  138.         return NULL;
  139.     }
  140.     op->ov_magic0 = op->ov_magic1 = MAGIC;
  141.     op->ov_index = 0xff;
  142. #ifdef MSTATS
  143.     nmalloc[NBUCKETS]++;
  144. #endif
  145. #ifdef RCHECK
  146.     /*
  147.      * Record allocated size of block and
  148.      * bound space with magic numbers.
  149.      */
  150.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  151.     op->ov_rmagic = RMAGIC;
  152.     *(unsigned short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  153. #endif
  154.     return (void *)(op+1);
  155.     }
  156.     /*
  157.      * Convert amount of memory requested into closest block size
  158.      * stored in hash buckets which satisfies request.
  159.      * Account for space used per block for accounting.
  160.      */
  161. #ifndef RCHECK
  162.     amt = 8;    /* size of first bucket */
  163.     bucket = 0;
  164. #else
  165.     amt = 16;    /* size of first bucket */
  166.     bucket = 1;
  167. #endif
  168.     while (nbytes + OVERHEAD > amt) {
  169.     amt <<= 1;
  170.     if (amt == 0) {
  171.         return (NULL);
  172.     }
  173.     bucket++;
  174.     }
  175.     ASSERT( bucket < NBUCKETS );
  176.  
  177.     /*
  178.      * If nothing in hash bucket right now,
  179.      * request more memory from the system.
  180.      */
  181.     if ((op = nextf[bucket]) == NULL) {
  182.     MoreCore(bucket);
  183.     if ((op = nextf[bucket]) == NULL) {
  184.         return (NULL);
  185.     }
  186.     }
  187.     /*
  188.      * Remove from linked list
  189.      */
  190.     nextf[bucket] = op->ov_next;
  191.     op->ov_magic0 = op->ov_magic1 = MAGIC;
  192.     op->ov_index = (unsigned char) bucket;
  193. #ifdef MSTATS
  194.     nmalloc[bucket]++;
  195. #endif
  196. #ifdef RCHECK
  197.     /*
  198.      * Record allocated size of block and
  199.      * bound space with magic numbers.
  200.      */
  201.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  202.     op->ov_rmagic = RMAGIC;
  203.     *(unsigned short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  204. #endif
  205.     return ((char *)(op + 1));
  206. }
  207.  
  208. /*
  209.  *----------------------------------------------------------------------
  210.  *
  211.  * MoreCore --
  212.  *
  213.  *    Allocate more memory to the indicated bucket.
  214.  *
  215.  * Results:
  216.  *    None.
  217.  *
  218.  * Side effects:
  219.  *    Attempts to get more memory from the system.
  220.  *
  221.  *----------------------------------------------------------------------
  222.  */
  223.  
  224. static void
  225. MoreCore(
  226.     int bucket)        /* What bucket to allocat to. */
  227. {
  228.     register union overhead *op;
  229.     register long sz;        /* size of desired block */
  230.     long amt;            /* amount to allocate */
  231.     int nblks;            /* how many blocks we get */
  232.  
  233.     /*
  234.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  235.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  236.      */
  237.     sz = 1 << (bucket + 3);
  238.     ASSERT(sz > 0);
  239.  
  240.     amt = MAXMALLOC;
  241.     nblks = amt / sz;
  242.     ASSERT(nblks*sz == amt);
  243.  
  244.     op = (union overhead *)TclpSysAlloc(amt, 1);
  245.     /* no more room! */
  246.     if (op == NULL) {
  247.     return;
  248.     }
  249.     
  250.     /*
  251.      * Add new memory allocated to that on
  252.      * free list for this hash bucket.
  253.      */
  254.     nextf[bucket] = op;
  255.     while (--nblks > 0) {
  256.     op->ov_next = (union overhead *)((caddr_t)op + sz);
  257.     op = (union overhead *)((caddr_t)op + sz);
  258.     }
  259.     op->ov_next = (union overhead *)NULL;
  260. }
  261.  
  262. /*
  263.  *----------------------------------------------------------------------
  264.  *
  265.  * TclpFree --
  266.  *
  267.  *    Free memory.
  268.  *
  269.  * Results:
  270.  *    None.
  271.  *
  272.  * Side effects:
  273.  *    None.
  274.  *
  275.  *----------------------------------------------------------------------
  276.  */
  277.  
  278. void
  279. TclpFree(
  280.     char *cp)        /* Pointer to memory to free. */
  281. {   
  282.     register long size;
  283.     register union overhead *op;
  284.  
  285.     if (cp == NULL) {
  286.     return;
  287.     }
  288.  
  289.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  290.  
  291.     ASSERT(op->ov_magic0 == MAGIC);        /* make sure it was in use */
  292.     ASSERT(op->ov_magic1 == MAGIC);
  293.     if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC) {
  294.     return;
  295.     }
  296.  
  297.     RANGE_ASSERT(op->ov_rmagic == RMAGIC);
  298.     RANGE_ASSERT(*(unsigned short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  299.     size = op->ov_index;
  300.     if ( size == 0xff ) {
  301. #ifdef MSTATS
  302.     nmalloc[NBUCKETS]--;
  303. #endif
  304.     TclpSysFree(op);
  305.     return;
  306.     }
  307.     ASSERT(size < NBUCKETS);
  308.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  309.     nextf[size] = op;
  310. #ifdef MSTATS
  311.     nmalloc[size]--;
  312. #endif
  313. }
  314.  
  315. /*
  316.  *----------------------------------------------------------------------
  317.  *
  318.  * TclpRealloc --
  319.  *
  320.  *    Reallocate memory.
  321.  *
  322.  * Results:
  323.  *    None.
  324.  *
  325.  * Side effects:
  326.  *    None.
  327.  *
  328.  *----------------------------------------------------------------------
  329.  */
  330.  
  331. char *
  332. TclpRealloc(
  333.     char *cp,            /* Pointer to alloced block. */
  334.     unsigned int nbytes)    /* New size of memory. */
  335. {   
  336.     int i;
  337.     union overhead *op;
  338.     int expensive;
  339.     unsigned long maxsize;
  340.  
  341.     if (cp == NULL) {
  342.     return (TclpAlloc(nbytes));
  343.     }
  344.  
  345.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  346.  
  347.     ASSERT(op->ov_magic0 == MAGIC);        /* make sure it was in use */
  348.     ASSERT(op->ov_magic1 == MAGIC);
  349.     if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC) {
  350.     return NULL;
  351.     }
  352.  
  353.     RANGE_ASSERT(op->ov_rmagic == RMAGIC);
  354.     RANGE_ASSERT(*(unsigned short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  355.     i = op->ov_index;
  356.  
  357.     /*
  358.      * If the block isn't in a bin, just realloc it.
  359.      */
  360.  
  361.     if (i == 0xff) {
  362.     op = (union overhead *) TclpSysRealloc(op, nbytes+OVERHEAD);
  363.     if (op == NULL) {
  364.         return NULL;
  365.     }
  366. #ifdef MSTATS
  367.     nmalloc[NBUCKETS]++;
  368. #endif
  369. #ifdef RCHECK
  370.     /*
  371.      * Record allocated size of block and update magic number bounds.
  372.      */
  373.  
  374.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  375.     *(unsigned short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  376. #endif
  377.     return (char *)(op+1);
  378.     }
  379.     maxsize = 1 << (i+3);
  380.     expensive = 0;
  381.     if ( nbytes + OVERHEAD > maxsize ) {
  382.     expensive = 1;
  383.     } else if ( i > 0 && nbytes + OVERHEAD < (maxsize/2) ) {
  384.     expensive = 1;
  385.     }
  386.  
  387.     if (expensive) {
  388.     void *newp;
  389.         
  390.     newp = TclpAlloc(nbytes);
  391.     if ( newp == NULL ) {
  392.         return NULL;
  393.     }
  394.     maxsize -= OVERHEAD;
  395.     if ( maxsize < nbytes )
  396.         nbytes = maxsize;
  397.     memcpy((VOID *) newp, (VOID *) cp, (size_t) nbytes);
  398.     TclpFree(cp);
  399.     return newp;
  400.     }
  401.     
  402.     /*
  403.      * Ok, we don't have to copy, it fits as-is
  404.      */
  405. #ifdef RCHECK
  406.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  407.     *(unsigned short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  408. #endif
  409.     return(cp);
  410. }
  411.  
  412. /*
  413.  *----------------------------------------------------------------------
  414.  *
  415.  * mstats --
  416.  *
  417.  *    Prints two lines of numbers, one showing the length of the 
  418.  *    free list for each size category, the second showing the 
  419.  *    number of mallocs - frees for each size category.
  420.  *
  421.  * Results:
  422.  *    None.
  423.  *
  424.  * Side effects:
  425.  *    None.
  426.  *
  427.  *----------------------------------------------------------------------
  428.  */
  429.  
  430. #ifdef MSTATS
  431. void
  432. mstats(
  433.     char *s)    /* Where to write info. */
  434. {
  435.     register int i, j;
  436.     register union overhead *p;
  437.     int totfree = 0,
  438.     totused = 0;
  439.  
  440.     fprintf(stderr, "Memory allocation statistics %s\nTclpFree:\t", s);
  441.     for (i = 0; i < NBUCKETS; i++) {
  442.     for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  443.         fprintf(stderr, " %d", j);
  444.     totfree += j * (1 << (i + 3));
  445.     }
  446.     fprintf(stderr, "\nused:\t");
  447.     for (i = 0; i < NBUCKETS; i++) {
  448.     fprintf(stderr, " %d", nmalloc[i]);
  449.     totused += nmalloc[i] * (1 << (i + 3));
  450.     }
  451.     fprintf(stderr, "\n\tTotal small in use: %d, total free: %d\n",
  452.         totused, totfree);
  453.     fprintf(stderr, "\n\tNumber of big (>%d) blocks in use: %d\n", 
  454.         MAXMALLOC, nmalloc[NBUCKETS]);
  455. }
  456. #endif
  457.